package com.arron.algorithm;

import java.util.Arrays;

/**
 * @Classname TreeNode
 * @Date 2020/9/13 12:34
 * @Created by 刘
 *  重构二叉树：
 *      输入某二叉树的前序遍历，中序遍历，输出重构的二叉树
 */
class TreeNode{
    //树的值
    public int val;
    //树的左节点
    public TreeNode left;
    //树的右节点
    public TreeNode right;
    public  TreeNode(int v){
        this.val = v;
    }
}

public class BinaryTreeDemo {

    private static TreeNode root;

    public static void main(String[] args) {

//        int[] ints = {3,4,2,1,5,6};
//        for (int i : ints) {
//            insertTreeNode(i);
//        }
//        System.out.println(ints);

        int[] pre ={1,2,4,7,3,5,6,8};
        int[] in = {4,7,2,1,5,3,8,6};
        TreeNode treeNode = reConstructBinaryTree(pre, in);
        System.out.println(treeNode);
    }

    /**
     * pre , in
     *输入前序遍历和中序遍历的结果,返回二叉树
     * @param pre
     * @param in
     * @return
     */
    public static TreeNode reConstructBinaryTree(int [] pre,int [] in) {

        //先判断二叉树是否为null;
        if (pre.length == 0){
            return null;
        }
        //拿到树的根节点
        int rootVal = pre[0];
        //如果pre的长度为一，又要特殊考虑
        if (pre.length == 1){
            return  new TreeNode(rootVal);
        }

        //拿到根节点的位置，从而确定好要遍历的左右子树的范围
        int rootIndex = 0;
        for (int i = 0; i < in.length; i++) {
            if (in[i] == rootVal){
                //找到根节点的下标位置
                rootIndex = i;
                break;
            }
        }

        TreeNode root = new TreeNode(rootVal);

        //最后递归遍历前序序列和后序序列，从而确定左右子树的范围

        //前序遍历顺序：ROOT + LEFT + RIGHT
        //中序遍历顺序：LEFT + ROOT + RIGHT
        root.left =  reConstructBinaryTree(Arrays.copyOfRange(pre,1,rootIndex+1),Arrays.copyOfRange(in,0,rootIndex));
        root.right = reConstructBinaryTree(Arrays.copyOfRange(pre,rootIndex+1,pre.length),Arrays.copyOfRange(in,rootIndex+1,in.length));

        //最后直接返回构造好的根节点
        return root;
    }

    /**
     * 构建二叉树
     */
    public static void insertTreeNode(int v){

            //先定义根节点,如果根节点为null,代表当前节点是第一个插入
            if (null == root){
                root  = new TreeNode(v);
                return;
            }else {
                //如果根节点已经定义了,让当前节点指向根节点
                TreeNode cur = root;
                TreeNode parent = null;

                //循环遍历树的
                while (true){
//            先让父节点指向当前节点
                    parent = cur;
                    //判断传进来的值是大于当前节点的值还是小于当前节点的值
                    if (cur.val>v){
                        //小于则应该放在当前节点的左子树中
                        cur = cur.left;
                        if (cur == null){
                            parent.left = new TreeNode(v);
                            //插入成功，退出循环
                            return;
                        }
                    }else {
                        //如果传进来的值是大于当前节点的值,就插入到当前节点的右子树中
                        cur = cur.right;
                        if (cur == null){
                            parent.right = new TreeNode(v);
                            //插入成功，退出循环
                            return;
                        }

                    }

                }


            }

    }



}
